// 栈
// "消消乐" 问题，要想到使用栈的思想解决
// 表达式求值问题 - 使用栈模拟计算过程，栈是一种思想，不局限于形式（可以是 stringBuilder， 也可以是 数组）
// 带括号的表达式 - 一般都需要用到双栈进行模拟
// 验证栈序列 - 使用栈模拟进栈出栈

// 例题 5：
// 给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。
//
//        示例 1：
//
//        输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
//        输出：true
//        解释：我们可以按以下顺序执行：
//        push(1), push(2), push(3), push(4), pop() -> 4,
//        push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
//        示例 2：
//
//        输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
//        输出：false
//        解释：1 不能在 2 之前弹出。
//
//        提示：
//
//        1 <= pushed.length <= 1000
//        0 <= pushed[i] <= 1000
//        pushed 的所有元素 互不相同
//        popped.length == pushed.length
//        popped 是 pushed 的一个排列

// 解题思路：
// 使用栈模拟进栈和出栈操作
// 如果最终栈为空，就表示栈序列正确，否则栈序列错误

import java.util.Stack;

public class ValidateStackSequences {
    // 解法 1：使用栈模拟 进栈 和 出栈 操作
    public boolean validateStackSequences1(int[] pushed, int[] popped) {
        int n = pushed.length;
        Stack<Integer> stack = new Stack<>();
        int i = 0; int j = 0;
        while(i < n){
            stack.push(pushed[i]);
            while(!stack.isEmpty() && stack.peek() == popped[j]){
                stack.pop();
                j++;
            }
            i++;
        }
        return stack.isEmpty();
    }
    // 解法 2：使用数组模拟 进栈 和 出栈 操作
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int n = pushed.length;
        int[] nums = new int[n];
        int pos = 0;
        int i = 0; int j = 0;
        while(i < n){
            nums[pos++] = pushed[i];
            while(pos > 0 && nums[pos - 1] == popped[j]){
                pos--;
                j++;
            }
            i++;
        }
        return pos == 0;
    }
}
